
// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
#include <string>
using namespace std;
class Codec
{
    // 中序遍历
public:
    // Encodes a tree to a single string.
    void __serialize(TreeNode *root, string &str)
    {
        if (!root)
        {
            str += "\"null\"";
            return;
        }
        str += "\"" + to_string(root->val) + "\"";
        __serialize(root->left, str);
        __serialize(root->right, str);
    }
    string serialize(TreeNode *root)
    {
        string res;
        __serialize(root, res);
        return res;
    }

    // Decodes your encoded data to tree.
    void __deserialize(TreeNode **root, string &data)
    {
        size_t start = data.find('\"');
        if (start == string::npos)
            return;
        size_t tail = data.find('\"', start + 1);
        size_t val_len = tail - start - 1;
        string val_str = data.substr(start + 1, val_len);
        data.erase(0, tail + 1);
        if (val_str == "null")
            return;
        *root = new TreeNode(stoi(val_str));
        __deserialize(&(*root)->left, data);
        __deserialize(&(*root)->right, data);
    }
    TreeNode *deserialize(string data)
    {
        if (data == "\"null\"")
            return nullptr;
        TreeNode *res = nullptr;
        __deserialize(&res, data);
        return res;
    }
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));